﻿using System;
using System.Collections.Generic;

namespace CoreLib
{
    /// <summary>
    /// A Generic tree data structure
    /// </summary>
    /// <typeparam name="T">The type to store in the tree</typeparam>
    public class Tree<T>
    {
        private readonly List<Tree<T>> _branches;
        private readonly T _value;

        /// <summary>
        /// Indexer into the branches of this tree (not recursive).
        /// </summary>
        /// <param name="key">The value of the branch to look for</param>
        /// <returns>The branch with the specified value (or null if not found)</returns>
        public Tree<T> this[T key]
        {
            get
            {
                return _branches.Find(branch => branch.Value.Equals(key));
            }
        }

        /// <summary>
        /// The branches of this tree
        /// </summary>
        public IEnumerable<Tree<T>> Branches
        {
            get { return _branches; }
        }

        /// <summary>
        /// The value for this branch/trunk of the tree
        /// </summary>
        public T Value
        {
            get { return _value; }
        }

        /// <summary>
        /// Creates the tree
        /// </summary>
        /// <param name="value">The value for this branch/trunk of the tree</param>
        public Tree( T value )
        {
            _value = value;
            _branches = new List<Tree<T>>();
        }

        /// <summary>
        /// Add a branch
        /// </summary>
        /// <param name="branch">The branch to add</param>
        public void AddBranch( Tree<T> branch )
        {
            _branches.Add( branch );
        }

        /// <summary>
        /// Add a branch
        /// </summary>
        /// <param name="branch">The object to create a new branch for</param>
        public void AddBranch( T branch )
        {
            AddBranch( new Tree<T>( branch ) );
        }

        /// <summary>
        /// Add a range of branches
        /// </summary>
        /// <param name="newBranches">The branches to add</param>
        public void AddBranches( IEnumerable<Tree<T>> newBranches )
        {
            _branches.AddRange( newBranches );
        }

        /// <summary>
        /// Add a range of branches
        /// </summary>
        /// <param name="newBranches">The objects to create new branhces for</param>
        public void AddBranches( IEnumerable<T> newBranches )
        {
            foreach( var branch in newBranches )
                AddBranch( branch );
        }

        /// <summary>
        /// Look recursively through the tree for something that causes the <paramref name="finder"/> to pass
        /// </summary>
        /// <param name="finder">The finder predicate</param>
        /// <returns>The found tree/branch, or null</returns>
        public Tree<T> FindRecursive( Func<T, bool> finder )
        {
            if( finder( Value ) )
            {
                return this;
            }
            foreach( var branch in _branches )
            {
                var found = branch.FindRecursive( finder );
                if( found != null )
                {
                    return found;
                }
            }
            return null;
        }

        /// <summary>
        /// Sorts, recursively
        /// </summary>
        /// <param name="comparison">The comparison used to sort.</param>
        public void Sort( Comparison<Tree<T>> comparison )
        {
            _branches.Sort( comparison );
            _branches.ForEach( branch => branch.Sort( comparison ) );
        }

        /// <summary>
        /// Provides a mechanism to recurse through the tree
        /// </summary>
        /// <param name="action">The action to yield to for each branch</param>
        public void ForEachRecursive( Action<Tree<T>> action )
        {
            ForEachRecursive( (tree, ancestry) => action(tree), new Stack<T>() );
        }

        /// <summary>
        /// Provides a mechanism to recurse through the tree while providing
        /// access to the current item's ancestry
        /// </summary>
        /// <param name="action">The action to yield to for each branch, providing the
        /// current item, and its ancestry.</param>
        public void ForEachRecursive( Action<Tree<T>, Stack<T>> action )
        {
            ForEachRecursive( action, new Stack<T>() );
        }

        private void ForEachRecursive( Action<Tree<T>, Stack<T>> action, Stack<T> ancestry )
        {
            action( this, ancestry );
            ancestry.Push( Value );
            _branches.ForEach( branch => branch.ForEachRecursive( action, ancestry ) );
            ancestry.Pop();
        }
    }
}
